package Array;//给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
//
// 请你找出符合题意的 最短 子数组，并输出它的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：nums = [2,6,4,8,10,9,15]
//输出：5
//解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,4]
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁴ 
// -10⁵ <= nums[i] <= 10⁵ 
// 
//
// 
//
// 进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？ 
// 
// 
// Related Topics 栈 贪心 数组 双指针 排序 单调栈 👍 843 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class findUnsortedSubarray {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        if(len <= 1) {
            return 0;
        }
        /**
         从左到右循环，记录最大值为 max，若 nums[i] < max,
         则表明位置 i 需要调整, 循环结束，记录需要调整的最大位置 i 为 high;
         同理，从右到左循环，记录最小值为 min, 若 nums[i] > min, 则表明位置 i 需要调整，循环结束，
         记录需要调整的最小位置 i 为 low.

         O(n) 时间复杂度 */
        int high = 0, low = len-1, max = nums[0], min = nums[len-1];
        for(int i = 1; i < len; i++){
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[len-1-i]);
            if(nums[i] < max) {
                high = i;
            }
            if(nums[len-1-i] > min) {
                low = len-1-i;
            }
        }
        return high > low ? high - low + 1 : 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
